import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class Tree {
        public char val;
        public Tree left;
        public Tree right;

        public Tree(char val) {
            this.val = val;
        }
    }

    public Tree GreatTree() {
        Tree A = new Tree('A');
        Tree B = new Tree('B');
        Tree C = new Tree('C');
        Tree D = new Tree('D');
        Tree E = new Tree('E');
        Tree F = new Tree('F');
        Tree G = new Tree('G');
        Tree H = new Tree('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    public Tree GreatTree2() {
        Tree B = new Tree('B');
        Tree D = new Tree('D');
        Tree E = new Tree('E');
        Tree H = new Tree('H');
        B.left = D;
        B.right = E;
        E.right = H;
        return B;
    }

    public Tree GreatTree3() {
        Tree B = new Tree('B');
        Tree D = new Tree('D');
        Tree E = new Tree('E');
        Tree H = new Tree('H');
        B.left = D;
        D.left = H;
        H.left = E;
        return B;
    }

    //检查两棵树是否相同
    public boolean isSameTree(Tree p, Tree q) {
        if (p == null && q != null) {
            return false;
        }
        if (q == null && p != null) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //是否是另一棵树的子树
    public boolean isSubtree(Tree root, Tree subRoot) {
        Boolean flg = false;
        if (root == null) {
            return false;
        }
        Boolean a = isSubtree(root.left, subRoot);
        Boolean b = isSubtree(root.right, subRoot);

        if (root.val == subRoot.val) {
            flg = isSameTree(root, subRoot);
        }
        if (flg == true) {
            return true;
        }
        return a || b;
    }

    //翻转二叉树
    public Tree invertTree(Tree root) {
        if (root == null) {
            return null;
        }
        Tree Node = root.left;
        root.left = root.right;
        root.right = Node;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public void TreeNode2(Tree root) {
        if (root == null) {
            return;
        }
        System.out.print(" " + root.val);
        TreeNode2(root.left);
        TreeNode2(root.right);
    }

    //求二叉树的高度
    int gethight(Tree root) {
        if (root == null) {
            return 0;
        }
        int lefthight = gethight(root.left);
        int righthight = gethight(root.right);
        if (lefthight > righthight) {
            return lefthight + 1;
        } else {
            return righthight + 1;
        }
    }

    //判断是否是平衡二叉树
    public boolean isBalanced(Tree root) {
        if (root == null) {
            return true;
        }
        int left = gethight(root.left);
        int right = gethight(root.right);
        if (Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        }
        return false;
    }
    //求二叉树的高度是否平衡
    int gethight2(Tree root) {
        if (root == null) {
            return 0;
        }
        int left = gethight2(root.left);
        if (left <= 0){
            return -1;
        }

        int right = gethight2(root.right);

        if (left > 0 && right > 0 && Math.abs(left - right) <= 1) {
            return Math.max(left,right) + 1;
        }
        return -1;
    }

    //判断是否是平衡二叉树
    public boolean isBalanced2(Tree root) {
        if (root == null){
            return true;
        }
        if (gethight2(root) <= 0){
            return false;
        }
        return true;
    }

    //判断是否是对称二叉树
    public boolean isSymmetric(Tree root){
        if (root == null){
            return true;
        }
        if (isSame(root.left,root.right)){
            return true;
        }
        return false;
    }
    //判断两棵树是否对称
    public boolean isSame(Tree p,Tree q){
        if (p == null && q != null){
            return false;
        }
        if (p != null && q== null){
            return false;
        }
        if (p == null && q == null){
            return true;
        }

        if (p.val != q.val){
            return false;
        }
        return isSame(p.left,q.right) &&isSame(p.right,q.left);
    }
    //判断是否是完全二叉树
    public boolean isCompleteTree(Tree root){
        if (root == null){
            return true;
        }
        Queue<Tree> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            Tree node = queue.poll();
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            Tree node2 = queue.peek();
            if (node2 != null){
                return false;
            }else {
                queue.poll();
            }
        }
        return true;
    }
    //二叉树的层序遍历
    public void levelOrder(Tree root){
        if (root == null){
            return;
        }
        Queue<Tree> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.size() != 0){
            Tree node = queue.poll();
            System.out.print(" " + node.val);
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return;
    }
}
